package sort.bucket;


import org.junit.Test;
import sort.util.SortUtil;

/**
 * 计数排序
 */
public class CountSort {
    @Test
    public void test() {
        int[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        nums = countSort2(nums);

        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    //版本2 实现稳定排序
    public int[] countSort2(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }

        int min = nums[0], max = nums[0];

        //找到最大、最小值
        for (int i = 0; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        //创建一个长度为 max-min+1的数组，用于计数
        int[] countArr = new int[max - min + 1];

        //填充 countArr数组
        for (int i = 0; i < nums.length; i++) {
            countArr[nums[i] - min]++; //计数
        }

        // 修改计数数组，每个元素值表示该元素在 排序后 数组的位置
        // 假设countArr[0]=3 countArr[1]=2 +3 == >5  表示值为 min+1 最后一个元素的位置在索引 5-1=4 处
        // 由后往前遍历countArr数组,并让其值-1,存放到排序的正确索引位置，这样做可以保证相同元素的先后顺序不会发生改变
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }

        //声明一个数组用于存放 排序后的数组
        int ans[] = new int[nums.length];

        //对原数组从后往前遍历
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = countArr[nums[i] - min] - 1;
            ans[index] = nums[i];
            countArr[nums[i] - min]--;
        }

        return ans;
    }

    //版本1 未实现其稳定排序
    public int[] countSort1(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }

        int min = nums[0], max = nums[0];

        //找到最大最小值
        for (int i = 0; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        //创建一个长度为 max-min+1的数组
        int[] countArr = new int[max - min + 1];

        //填充 countArr数组
        for (int i = 0; i < nums.length; i++) {
            countArr[nums[i] - min]++; //计数
        }

        //创建一个新数组来存储已经排序完成的结果
        int begin = 0; //指向新数组的索引

        // 这里的时间复杂度不是O(n^2),而是O(n+k)
        for (int i = 0; i < countArr.length; i++) {     // O(k)
            if (countArr[i] != 0) {
                for (int j = 0; j < countArr[i]; j++) { // countArr元素总和是 nums数组的长度 O(n)
                    nums[begin++] = min + i; //i+min才是真实的值
                }
            }
        }
        return nums;
    }
}
